『AGC 023A』Zero-Sum Ranges

Problem

Time limit : 2sec / Memory limit : 256MB

我们有一个整数序列$A$，其长度是$N$

请找出其总和为$0$的$A$的非空邻接子序列的数目。请注意，我们正在计算取出子序列的方法。也就是说，即使某些两个子序列的内容相同，如果它们取自不同的位置，则对它们进行单独计数。

door♂

Solution

• $n^2$的算法会超时

首先看样例

下标	1	2	3	4	5	6
数字	1	3	-4	2	2	-2
前缀和	1	4	0	2	4	2

我们可以发现相同的两个数之间之间经过的数的和一定是$0$；
例如第一个$4$和第二个$4$ 之间是 $-4 + 2 +2=0$所以我们发现规律：

• 只要找到相同的数的个数让他们之间两两连接就是个数
  如果和为$0$代表从第一个开始到它的和就是$0$所以要额外加上$0$的个数

懒得离散化就用map，反正能过233

Code:

复制

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>
#define MAXN 200010
using namespace std;
typedef long long ll;
int N;
ll A[MAXN];
map <ll, int> M;
inline void _read(int &x)
{
	x = 0;
	register int y = 1;
	char t = getchar();
	while (!isdigit(t) && t != '-') t = getchar();
	if (t == '-')
	{
		y = -1;
		t = getchar();
	}
	while (isdigit(t))
	{
		x = x * 10 + t - '0';
		t = getchar();
	}
	x *= y;
}
inline void _read(ll &x)
{
	x = 0;
	register ll y = 1;
	char t = getchar();
	while (!isdigit(t) && t != '-') t = getchar();
	if (t == '-')
	{
		y = -1;
		t = getchar();
	}
	while (isdigit(t))
	{
		x = x * 10 + t - '0';
		t = getchar();
	}
	x *= y;
}
int main()
{
	_read(N);
	for (int i = 1; i <= N; ++i) _read(A[i]);
	M[0] = 1;
	ll ans = 0;
	for (int i = 1; i <= N; ++i)
	{
		A[i] += A[i - 1];
		ans += M[A[i]];
		M[A[i]] += 1;
	}
	printf("%lld\n", ans);
	return 0;
}